
#include <iostream>
#include <fstream>
#include "lklist.h"

using namespace std;

typedef int elemtype;
typedef lklisttpl<elemtype> lklist;

lklist *intersection( lklist *, lklist * );
lklist *intersection2( lklist *, lklist * );

int main()
{
    ifstream in("in.txt");
    vector<elemtype> va, vb;
    lklist *ha, *hb, *hc;
    int i, n;
    int t;

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	va.push_back(t);
    }

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	vb.push_back(t);
    }

    ha = createlk<lklist,elemtype>( va, WITHHEAD );
    printlk( ha, WITHHEAD ); cout << endl;

    hb = createlk<lklist,elemtype>( vb, WITHHEAD );
    printlk( hb, WITHHEAD ); cout << endl;

    hc = intersection2( ha, hb );
    printlk( hc, WITHHEAD ); cout << endl;

    destorylk( ha, WITHHEAD );
    destorylk( hb, WITHHEAD );
    destorylk( hc, WITHHEAD );

    return 0;
}


/* ******************************************************
 *             Answer to this question.
 * ******************************************************/

lklist *intersection( lklist *a, lklist *b )
{
    lklist *p, *q, *r, *t;
    
    lklist *c = new lklist;
    c->next = NULL;
    p = a->next;
    q = b->next;
    r = c;
    while( p && q ){ 
	while( q && q->data<p->data ) q = q->next;
	if( q && p->data == q->data ){
	    t = new lklist;
	    t->data = p->data;
	    t->next = r->next;
	    r->next = t;
	    r = r->next;
	}
	p = p->next;
    }
    
    return c;
}

lklist *intersection2( lklist *a, lklist *b )
{
    lklist *p, *q, *r, *t;
    
    lklist *c = new lklist;
    c->next = NULL;
    p = a->next;
    q = b->next;
    r = c;
    while( p && q ){
	
	if( p->data < q->data ) p = p->next;
	else if( p->data > q->data ) q = q->next;
	else{
	    t = new lklist;
	    t->data = p->data;
	    t->next = r->next;
	    r->next = t;
	    r = r->next;
	    p = p->next;
	    q = q->next;
	}
	
    }
	
    return c;
}
